class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

class Solution:
	# @param node, a undirected graph node
	# @return a undirected graph node
	def cloneGraph(self, node):
		if node is None:
			return None
		nodes = {}
		stk = [node]
		HEAD = node.label
		while len(stk) > 0:
			top = stk.pop()
			l = top.label
			if top.label not in nodes:
				nodes[l] = UndirectedGraphNode(l)
			for nb in top.neighbors:
				if nb.label not in nodes:
					stk.append(nb)
					nodes[nb.label] = UndirectedGraphNode(nb.label)
				nodes[l].neighbors.append(nodes[nb.label])
		return nodes[HEAD]

if __name__ == '__main__':
	n0 = UndirectedGraphNode(0)
	n1 = UndirectedGraphNode(1)
	n2 = UndirectedGraphNode(2)
	n3 = UndirectedGraphNode(3)

	n0.neighbors = [n1, n2]
	n1.neighbors = [n0, n2, n3]
	n2.neighbors = [n0, n1, n3]
	n3.neighbors = [n1, n3]

	so = Solution()
	nn = so.cloneGraph(n0)
	for nb in nn.neighbors[0].neighbors[2].neighbors:
		print nb.label

 